#include <iostream>
#include <ctime>

const int capacity = 10;

class MinHeap
{
public:
    MinHeap() : size(0) {}
    void Insert(int value)
    {
        if (size == capacity)
            return;
        array[size] = value;
        SifwUp(size);
        size++;
    }

    void Remove() // 根和要删的互换，删完之后再下沉
    {
        if (size == 0)
            return;
        array[0] = array[--size];
        SiftDown(0);
    }

    int *GetRoot() // 取根
    {
        if (size == 0)
            return nullptr;
        return &array[0];
    }

    void show()
    {
        for (int i = 0; i < size; i++)
        {
            std::cout << array[i] << " ";
        }
        std::cout << std::endl;
    }

private:
    int GetParent(int i) { return (i - 1) / 2; }
    int GetLeftChild(int i) { return 2 * i + 1; }
    int GetRightChild(int i) { return 2 * i + 2; }

    void SifwUp(int i) // 上浮       // log(n)(走树的高度)
    {
        while (i > 0 && array[i] < array[GetParent(i)]) // 保证有根(i > 0)
        {
            std::swap(array[i], array[GetParent(i)]);
            i = GetParent(i); // 我上浮之后还要继续向前走
        }
    }

    void SiftDown(int i) // 下沉操作
    {
        int left = GetLeftChild(i);
        int right = GetRightChild(i);

        int min = i; //
        if (left < size && array[left] < array[min])
        {
            min = left;
        }
        if (right < size && array[right] < array[min])
        {
            min = right;
        }
        if (min != i) // i下沉了
        {
            std::swap(array[i], array[min]);
            SiftDown(min); // 递归下沉
        }
    }

    int array[capacity];
    int size;
};

int main()
{
    srand(time(nullptr));
    int a[20] = {0};
    for (int i = 0; i < 20; i++)
    {
        a[i] = std::rand() % 100;
        std::cout << a[i] << " ";
    }
    std::cout << std::endl;

    MinHeap h;
    for (int i = 0; i < 5; i++)
        h.Insert(a[i]);
    for (int i = 0; i < 20; i++)
    {
        if (a[i] > *h.GetRoot())  
        {
            h.Insert(a[i]); 
            h.Remove();  
        }
    }
    h.show();

    return 0;
}                      
